#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2023/3/27 10:40
# @Author : Sugar丶fate

import math
import pandas as pd

def Distance(x,y,X,Y):
    d = math.sqrt((X-x)**2+(Y-y)**2)
    return d


def get_vertical_dist(df,start_index,end_index,index):  # 得到垂直距离
    '''

    :param df:  表格
    :param start_index: 起点
    :param end_index: 终点
    :param index:
    :return:
    '''
    a=math.fabs(Distance(df['x'][start_index],df['y'][start_index],df['x'][end_index],df['y'][end_index])) # 开始结束两点间的距离
    #当弦两端重合时,点到弦的距离变为点间距离
    if a==0:
        return math.fabs(Distance(df['x'][start_index],df['y'][start_index],df['x'][index],df['y'][index]))
    b=math.fabs(Distance(df['x'][start_index],df['y'][start_index],df['x'][index],df['y'][index]))
    c=math.fabs(Distance(df['x'][end_index],df['y'][end_index],df['x'][index],df['y'][index]))
    p=(a+b+c)/2
    S=math.sqrt(math.fabs(p*(p-a)*(p-b)*(p-c)))

    vertical_dist=S*2/a
    return vertical_dist


def DP_compress(df,output_point_list,Dmax):


    start_index = 0
    end_index = len(df['x']) - 1
    # 起止点必定是关键点,但是作为递归程序此步引入了冗余数据,后期必须去除
    output_point_list.append(df.iloc[start_index].values)
    output_point_list.append(df.iloc[end_index].values)


    if start_index<end_index:
        index=start_index+1        #工作指针,遍历除起止点外的所有点
        max_vertical_dist=0        #路径中离弦最远的距离
        key_point_index=0        #路径中离弦最远的点,即划分点

        while (index < end_index):
            cur_vertical_dist = get_vertical_dist(df,start_index,end_index,index)
            if cur_vertical_dist > max_vertical_dist:
                max_vertical_dist = cur_vertical_dist
                key_point_index = index  # 记录划分点

            index += 1
        # print(max_vertical_dist)
        # print(key_point_index)
        # print('_________________________')

        # 递归划分路径
        if max_vertical_dist >= Dmax:
            df1 = df.iloc[start_index:key_point_index].values
            df1 = pd.DataFrame(df1)
            # df1.columns = ['mmsi','lon','lat','v','c','time']
            df1.columns =  ['id','time', 'x', 'y', 'c']
            df2 = df.iloc[key_point_index:end_index].values
            df2 = pd.DataFrame(df2)
            # df2.columns = ['mmsi','lon','lat','v','c','time']
            df1.columns = ['id','time', 'x', 'y', 'c']
            DP_compress(df1, output_point_list, Dmax)
            DP_compress(df2, output_point_list, Dmax)
    return output_point_list



if __name__ == '__main__':
    df = open('data_临时.csv')
    df = pd.read_csv(df)
    df.columns = ['id', 'time', 'x', 'y', 'c']
    output_point_list = []
    output_point_list = DP_compress(df,output_point_list,0.09)
    print(output_point_list)